← All Articles

[SW Expert Academy] 3421. 수제 버거 장인

Posted on

문제 :

우리의 수제 버거 장인 화섭이는 신 메뉴를 개발하려고 한다.

화섭이가 사용할 수 있는 재료는 1번부터 N번까지 번호가 매겨져서 총 N가지가 있다.

화섭이는 가능한대로 많은 종류의 버거를 만들고 싶어 하지만 서로 어울리지 않는 재료들이 있기 때문에 이를 고려해야 한다.

i번 재료와 j번 재료가 서로 궁합이 맞지 않는다면 이들을 동시에 포함한 버거는 만들 수 없다.

이렇게 궁합이 맞지 않는 재료들로 M개쌍에 대한 정보가 주였을 때 화섭이가 만들 수 있는 버거의 종류가 몇 가지가 되는지 출력하라

(어떤 두 버거가 정확하게 같은 종류의 재료들을 사용한다면 두 버거는 같은 종류의 버거로 본다.)


입력 :

맨 위 줄에 테스트케이스의 개수가 주어진다.

각 테스트케이스 별로 순서대로 첫째 줄에 두 개의 정수 N, M (1 ≤ N ≤ 20, 0 ≤ M ≤ 400)이 주어진다.

다음 M개의 줄에는 서로 다른 두 개의 숫자 a, b (1 ≤ a, b ≤ N)가 주어지고 이들은 재료 a 번과 b 번이 동시에 같은 버거에 들어가면 안 된다는 것을 의미한다.

주어지는 쌍들은 모두 다르지는 않고, 즉 같은 쌍이 여러 번 주어질 수도 있다.


출력 :

각 테스트케이스 별로 순서대로 한 줄씩 답을 출력하는데, 제약조건을 만족시키며 만들 수 있는 버거의 가짓수를 출력한다.



풀이 :

완전 탐색은 2^20의 시간복잡도를 가질 뿐더러 어울리지 않는 조합 갯수가 최대 400종류가 있기 때문에 이 종류들을 모두 확인해준다면 시간초과를 피할 수 없는 문제이다.

따라서 본 문제는 효과적으로 백트래킹 로직을 사용하여야 문제를 해결할 수 있었다.

내가 사용한 방식은 n자리 2진수로 각각의 자리에 재료 하나씩을 비트마스킹한 꼴로 가정한 후 첫번째 재료부터 0과 1로 사용 유무를 선택해 탐색하는데 → 여기서 현재 조합에서 이미 어울리지 않는 조합이 포함되어 있는 경우에는 더 이상 탐색하지 않도록 구현하였다.

이렇게 백트래킹을 사용할 시 불필요한 조합들은 사전에 제외되어 경우의 수를 확실히 줄일 수 있었다.

현재 조합에서 어울리지 않는 조합이 있는 것을 찾아 내는 것에는 현재 사용유무를 결정할 재료보다 작은 인덱스를 가진 재료들 중 어울리지 않는 조합인 재료들만 따로 벡터에 저장해두어 체크해 주었다.



코드 :

코드 보기/접기 
#include<iostream>
#include<vector>
#include<cstring>

using namespace std;
vector<vector<int>> notsuits;
bool recorded[201][201];
int anscnt, n;

void possibleCombi(int idx, int curnum) {
    if(idx >= n) {
        anscnt++;
        return;
    }
    
    possibleCombi(idx + 1, curnum);
    
    int size = notsuits[idx].size();
    for(int k=0; k<size; k++){
        if(curnum & (1 << notsuits[idx][k])) return;
    }
    possibleCombi(idx + 1, curnum | (1 << idx));
}

void testCase() {
    int m, fir, sec;
    cin >> n >> m;
    
    notsuits.clear();
    notsuits.resize(n + 1);
    memset(recorded, false, sizeof(recorded));
    anscnt = 0;
    
    while(m--) {
        cin >> fir >> sec;
        fir--;
        sec--;
        if(fir>sec){
            if(!recorded[fir][sec]){
                recorded[fir][sec] = true;
                notsuits[fir].push_back(sec);
            }
        } else {
            if(!recorded[sec][fir]) {
                recorded[sec][fir] = true;
                notsuits[sec].push_back(fir);
            }
        }
    }
    
    possibleCombi(0, 0);
}

int main(int argc, char** argv)
{
    int test_case, T;
    cin>>T;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        testCase();
        cout << '#' << test_case << ' ' << anscnt << '\n';
    }
    return 0;
}


AlgorithmalgorithmSW ExpertC++